class Solution {
 public:
  // 1. dp[i][j]为走到(i,j)时的路径总数
  // 2. dp[i][j]=dp[i-1][j]+dp[i][j-1];  // 推出3，4，及是否能够空间优化
  // 3. dp[*][0]=1,dp[0][*]=1;
  // 4. i:0->m,j:0->n. 从左到右一层一层遍历
  // 5. 检查dp数组
  /*
  int uniquePaths(int m, int n) {
      vector<vector<int>> dp(m,vector<int>(n));
      int i,j;
      for(i=0;i<m;i++)
          dp[i][0]=1;
      for(i=0;i<n;i++)
          dp[0][i]=1;
      for(i=1;i<m;i++) {
          for(j=1;j<n;j++) {
              dp[i][j]=dp[i-1][j]+dp[i][j-1];
          }
      }
      return dp[m-1][n-1];
  }
  */
  // 空间优化,二维数组压缩为一维数组
  int uniquePaths(int m, int n) {
    vector<int> dp(n);
    for (int i = 0; i < n; i++) dp[i] = 1;
    int i, j;
    for (i = 1; i < m; i++) {
      for (j = 1; j < n; j++) {
        dp[j] += dp[j - 1];
      }
    }
    return dp[n - 1];
  }
};